package com.sparrow.common.util;

import java.util.BitSet;

/**
 * 布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，用于检测一个元素是否在一个集合中。
 * 它的特点是：
 * 如果布隆过滤器判断元素不存在，那它一定不存在。
 * 如果判断元素存在，那有一定概率是错误的（即可能存在假阳性，false positive）。
 * 简单来说，布隆过滤器可以快速判断“可能有”或者“一定没有”，但不能100%准确判断“有”。
 *
 * 基本原理：
 * 有一个很长的位数组（比如几百万位，全部初始化为0）。
 * 配置多个不同的哈希函数（比如 3-7 个），每个哈希函数可以把输入映射成一个整数（位数组的下标）。
 * 添加元素时，把这个元素用多个哈希函数分别哈希，得到几个位置，把这些位置上的比特位设为1。
 * 查询元素时，同样用所有哈希函数哈希，去检查对应的几个位是否都是1。
 * 如果有一个位是0，说明元素一定不存在。
 * 如果所有位都是1，说明元素可能存在。
 *
 * 布隆过滤器的误判，是因为哈希碰撞和位数组共享导致的，不是因为哈希函数本身出错。
 *常用于防止缓存穿透，请求快速拒绝
 */
public class BloomFilter<T> {
    private static final int DEFAULT_SIZE = 1 << 24; // 位数组大小，大约 16MB
    private static final int[] SEEDS = {7, 11, 13, 31, 37, 61}; // 哈希函数的种子

    private BitSet bitSet = new BitSet(DEFAULT_SIZE); // 位数组
    private SimpleHash[] hashFunctions = new SimpleHash[SEEDS.length]; // 多个哈希函数

    public BloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            hashFunctions[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    // 添加元素
    public void add(T value) {
        for (SimpleHash f : hashFunctions) {
            bitSet.set(f.hash(value));
        }
    }

    // 查询元素是否存在
    public boolean mightContain(T value) {
        for (SimpleHash f : hashFunctions) {
            if (!bitSet.get(f.hash(value))) {
                return false;
            }
        }
        return true;
    }

    // 简单哈希函数
    static class SimpleHash {
        private int cap;  // 位数组大小
        private int seed; // 哈希种子

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(Object value) {
            int h = value.hashCode();
            return (seed * h & 0x7fffffff) % cap;
        }
    }

    // 简单测试
    public static void main(String[] args) {
        BloomFilter<String> bf = new BloomFilter<>();

        bf.add("apple");
        bf.add("banana");
        bf.add("cherry");

        System.out.println(bf.mightContain("apple"));  // true
        System.out.println(bf.mightContain("banana")); // true
        System.out.println(bf.mightContain("cherry")); // true
        System.out.println(bf.mightContain("durian")); // 可能 false，也可能误判 true
    }
}

